/*
https://leetcode-cn.com/problems/super-ugly-number/solution/chao-ji-chou-shu-by-leetcode-solution-uzff/
 */
import java.util.Arrays;

public class Solution313 {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] dp=new int[n+1];
        int m=primes.length;
        int[] link=new int[m];
        Arrays.fill(link,1);
        dp[1]=1;
        for (int i=2;i<=n;i++){
            dp[i]=Integer.MAX_VALUE;
            for (int j=0;j<m;j++){
                dp[i]=Math.min(dp[i],dp[link[j]]*primes[j]);
            }
            for (int j=0;j<m;j++){
                if (dp[i]==dp[link[j]]*primes[j]){
                    link[j]++;
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution313().nthSuperUglyNumber(12,new int[]{2,7,13,19}));
    }
}
